Agent Communication

We cover agent communications, KIF, KQML, and FIPA-ACL. This talk summarizes:

• Michael Wooldridge. Introduction to MultiAgent Systems. [1] John Wiley and Sons;. 2002. Chapter 8
• FIPA ACL Message Structure Specification. [2] 2002.
• FIPA Communicative Act Library Specification. [3] 2002.
• FIPA Contract Net Interaction Protocol Specification. [4] 2002.
• FIPA Iterated Contract Net Interaction Protocol Specification. [5] 2002.
• FIPA English Auction Interaction Protocol Specification. [6] 2001.
• James Odell, H. Van Dyke Parunak, and Bernhard Bauer. Representing Agent Interaction Protocols in UML. [7] Paolo Ciancarini and Michael Wooldridge ed.In Agent-Oriented Software Engineering, p. 121--140, Springer-Verlag. 2001.

• Processes need to synchronize. e.g., when updating a shared variable.
• In OOP messaging is done by invoking member functions—object.msg()
• Autonomous agents can say no.
• So, all one can do is try to influence the agent to doing something.

• Speech Acts were introduced by John Austin [8].
• They have the characteristic of actions in that their utterance changes the world in an analogous way to physical actions.
• He identified a number of performative verbs which correspond to different types of speech acts.
  • request
  • inform
  • promise
• He also distinguished three aspecs of speech acts

1. locutionary act- the act of making an utterance.
2. illocutionary act- the action performed in saying something.
3. perlocution- the effect of the act

• If I say: “I will teach you the beauty of multiagent systems”
• locutionary- is the actual speaking I did.
• illocutionary- is the promise I made to you
• perlocution- is the effects it had on you. Hopefully, to convince you that I am here with a precise purpose.

• The work on speech acts was extend by John Searle [9] on his "Speech Acts" (1969) book.
• He attempted to classify speech acts into five classes.

1. Representatives- commit the speaker to the truth of an expressed proposition. (informing)
2. Directives- attempts on the part of the speaker to get the hearer to do something (request).
3. Commissives- commit the speaker to a course of action (promise).
4. Expressives- express some psychological state (thanking).
5. Declarations- effect some changes in an institutional state of affairs. (declare marriage).

• KIF [10] grew out of a the DARPA-funded Knowledge Sharing Effort [11]
• It is basically first-order logic in lisp format.
• It is meant to be a content language.
• Agents can define properties of things in a domain as well as relationships between things and general properties of the domain.
• For example, the sentences shown below encode 3 tuples in a personnel database
(salary 015-46-3946 widgets 72000)
(salary 026-40-9152 grommets 36000)
(salary 415-32-4707 fidgets 42000)
• The following sentence states that one chip is larger than another:
(> (* (width chip1) (length chip1))
(* (width chip2) (length chip2)))
• This one asserts that the number obtained by raising any real--number ?x to an even power ?n is positive:
(=> (and (real-number ?x)
(even-number ?n))
(> (expt ?x ?n) 0))
• This one says that on object is a bacher if it is a man and is not married
(defrelation bachelor (?x) :=
  (and (man ?x)
    (not (married ?x))))
• This one says that anyone who is a person is also a mammal
(defrelation person (?x) :=> (mammal ?x))

• KQML [12] is a language for communications. It is also part of the KSE.
• Each message starts with a performative and has a number of parameters. It looks like:
(ask-one
  :content (PRICE IBM ?price)
  :receiver stock-server
  :language LPROLOG
  :ontology NYSE-TICKS)

• An example dialogue: (evaluate
  :sender A :receiver B
  :language KIF :ontology motors
  :reply-with q1 :content (val (torque m1)))

(reply
  :sender B :receiver A
  :language KIF :ontology motors
  :in-reply-to q1 :content (= (torque m1) (scalar 12 kgf)))

• (stream-about
  :sender A :receiver B
  :language KIF :ontology motors
  :reply-with q1 :content m1)

(tell
  :sender B :receiver A
  :in-reply-to q1 :content (= (torque m1) (scalar 12 kgf)))

(tell
  :sender B :receiver A
  :in-reply-to q1 :content (= (status m1) normal))

(eos
  :sender B :receiver A
  :in-reply-to q1)

• The Foundation for Intelligent Physical Agents was founded on 1995.
• They developed new Agent Communication Language, based on what was learned on KQML (they are similar).

Element	Description	Category of Elements
performative	Denotes the type of the communicative act of the ACL message	Type of communicative acts
sender	Denotes the identity of the sender of the message, i.e. the name of the agent of the communicative act.	Participant in communication
receiver	Denotes the identity of the intended recipients of the message.	Participant in communication
reply-to	This element indicates that subsequent messages in this conversation thread are to be directed to the agent named in the reply-to element, instead of to the agent named in the sender element.	Participant in communication
content	Denotes the content of the message; equivalently denotes the object of the action.	Content of message
language	Denotes the language in which the content element is expressed.	Description of Content
encoding	Denotes the specific encoding of the content language expression.	Description of Content
ontology	Denotes the ontology(s) used to give a meaning to the symbols in the content expression.	Description of Content
protocol	Denotes the interaction protocol that the sending agent is employing with this ACL message.	Control of conversation
conversation-id	Introduces an expression (a conversation identifier) which is used to identify the ongoing sequence of communicative acts that together form a conversation.	Control of conversation
reply-with	Introduces an expression that will be used by the responding agent to identify this message.	Control of conversation
in-reply-to	Denotes an expression that references an earlier action to which this message is a reply.	Control of conversation
reply-by	Denotes a time and/or date expression which indicates the latest time by which the sending agent would like to havereceived a reply.	Control of conversation

• The only element that is mandatory is the performative, but most will also contain sender, receiver, and content elements.
• If an agent does not recognize or is unable to process one or more of the elements or element values, it can reply with the appropriate not-understood

• They are listed in the FIPA Communicative Act Library Specification.
• accept-proposal- The action of accepting a previously submitted propose to perform an action.
• agree- The action of agreeing to perform a requestd action made by another agent. Agent will carry it out.
• cancel- Agent wants to cancel a previous request.
• cfp- Agent issues a call for proposals. It contains the actions to be carried out and any other terms of the agreement.
• confirm- The sender confirms to the receiver the truth of the content. The sender initially believed that the receiver was unsure about it.
• disconfirm- The sender confirms to the receiver the falsity of the content.
• failure- Tell the other agent that a previously requested action failed.
• inform- Tell another agent something. The sender must believe in the truth of the statement. Most used performative.
• inform-if- Used as content of request to ask another agent to tell us is a statement is true or false.
• inform-ref- Like inform-if but asks for the value of the expression.
• not-understood- Sent when the agent did not understand the message.
• propagate- Asks another agent so forward this same propagate message to others.
• propose- Used as a response to a cfp. Agent proposes a deal.
• proxy- The sender wants the receiver to select target agents denoted by a given description and to send an embedded message to them.
• query-if- The action of asking another agent whether or not a given proposition is true.
• query-ref- The action of asking another agent for the object referred to by an referential expression.
• refuse- The action of refusing to perform a given action, and explaining the reason for the refusal.
• reject-proposal- The action of rejecting a proposal to perform some action during a negotiation.
• request- The sender requests the receiver to perform some action. Usually to request the receiver to perform another communicative act.
• request-when- The sender wants the receiver to perform some action when some given proposition becomes true.
• request-whenever- The sender wants the receiver to perform some action as soon as some proposition becomes true and thereafter each time the proposition becomes true again.
• subscribe- The act of requesting a persistent intention to notify the sender of the value of a reference, and to notify again whenever the object identified by the reference changes.

• The semantics are given using a formal (logical) language called SL, which uses beliefs, desires, and uncertain beliefs.
• FP: is the feasability precondition which the sender of the message must satisfy in order to send this message.
• RE: is the rational effect of the action—the purpose of the message. It cannot be guaranteed since agents are autonoumous and rational.
• All FIPA-ACL performative semantics are defined in terms of inform and request. <i, inform(j,φ)>
  FP: Biφ ∧ ¬Bi(Bifjφ ∨ Uijjφ)
  RE: Bjφ

<i,request(j,α)>
  FP: BiAgent(α,j) ∧ ¬BiIjDone(α)
  RE: Done(α)

• Bifφ means that agent i has a definite opinion about the truth or falsity of φ
• Uif_iφ means that i is uncertain about φ
• Agent(α,j) means that the agent of action α is j.
• Aside: There is currently some controversy about the feasability of verifying whether a system obeys the ACL semantics; since it uses mental states the only way to verify is by examining the agents' mental states.

Summary	The action of calling for proposals to perform a given action.
Message Content	A tuple containing an action expression denoting the action to be done, and a referential expression defining a single-parameter proposition which gives the preconditions on the action.
Description	CFP is a general-purpose action to initiate a negotiation process by making a call for proposals to perform the given action. The actual protocol under which the negotiation process is established is known either by prior agreement, or is explicitly stated in the:protocol parameter of the message.   In normal usage, the agent responding to acfp should answer with a proposition giving the value of the parameter in the original precondition expression (see the statement ofcfp's rational effect). For example, thecfp might seek proposals for a journey from Frankfurt to Munich, with a condition that the mode of travel is by train. A compatible proposal in reply would be for the 10.45 express train. An incompatible proposal would be to travel by airplane.   Note thatcfp can also be used to simply check the availability of an agent to perform some action. Also note that this formalization ofcfp is restricted to the common case of proposals characterized by a single parameter (x) in the proposal expression. Other scenarios might involve multiple proposal parameters, demand curves, free-form responses, and so forth.
Formal Model	<i, cfp (j, <j, act>, Ref x φ(x))> ≡   <i, query-ref (j, Ref x (Ii Done (<j, act>, φ(x)) ⇒     (Ij Done (<j, act>, φ(x))))> FP: ¬Bref(Ref x α(x)) ∧ ¬Urefi(Ref x α(x)) ∧   ¬Bi Ij Done (<j, inform-ref (i, Ref x α(x))>) RE: Done (<j, inform (i, Ref x α(x) = r1)> | … |   <j, inform (i, Ref x α(x) = rk)>) Where: α(x) = Ii Done (<j, act>, φ(x)) ⇒ Ij Done (<j, act>, φ(x)) Agent i asks agent j: "What is the 'x' such that you will perform action 'act' when 'φ (x)' holds?" Note: Ref x δ(x) is one of the referential expressions: one δ(x), any x δ(x) or all x δ(x). Note: The RE of this is not a proposal by the recipient. Rather, it is the value of the proposal parameter. See the example in the definition of the propose act.
Example	Agentj asksi to submit its proposal to sell 50 boxes of plums. (cfp  :sender (agent-identifier :name j)     :receiver (set (agent-identifier :name i))   :content ((action (agent-identifier :name i)     (sell plum 50)) (any ?x (and (= (price plum) ?x) (< ?x 10))))   :ontology fruit-market)

• They are typical patters of message exchange.
• A designer of agent systems has the choice to make the agents sufficiently aware of the meanings of the messages and the goals, beliefs and other mental attitudes the agent possesses, and that the agent's planning process causes such IPs to arise spontaneously from the agents' choices. This is hard to do!
• IPs are given pre-defined names.
• A FIPA ACL-compliant agent need not implement any of the standard IPs, nor is it restricted from using other IP names. However, if one of the standard IP names is used, the agent must behave consistently with the IP specification given here.

• Needed because UML lacks support for agents since they run on their own thread.
• FIPA calls IP representation in AUML, Protocol Diagrams (PD).
• The vertical dimension is time, proceeding down the page.

• Agents can perform various roles within on IP. e.g., in contract-net the buyer and seller roles could be played by one agent, at different times.
• A protocol can be defined between different concrete agent instances or a set of agents satisfying a distinguished role and/or class. An agent satisfying a distinguished AgentRole and class is called agent of a given AgentRole and class, respectively.
• An AgentRole is shown as a rectangle that is filled with some string of one of the following forms:

  • Seller

    role: This denotes arbitrary agents satisfying the distinguished AgentRole.

  • Seller-1/Seller, Buyer

    instance / role-1 ... role-n: This denotes a distinguished agent instance that satisfies the AgentRoles 1-n where n>0.

  • Seller-1/Seller, Buyer:ComercialAgent

    instance / role-1 ... role-n : class: This denotes a distinguished agent instance that satisfied the AgentRoles 1-n where n>0 and class it belongs to.

• The agent lifeline defines the time period when an agent exists.
• An agent lifeline is shown as a vertical dashed line.
• Lifelines can be split to show AND/OR parallelism:
  • AND parallelism starts at a horizontal heavy bar.
  • OR parallelism (inclusive-or) starts at a horizontal heavy bar with a non-filled diamond, and,
  • decision (exclusive-or) starts at a horizontal heavy bar with a non-filled diamond with "x" inside the diamond and is continued with a set of parallel vertical lifelines connected to the heavy bar.

• Since the behaviour of an AgentRole depends on the incoming message and different communicative acts are allowed as an answer to a communicative act, the thread of interaction, that is, the processing of incoming messages, has to be split up into different threads of interaction. The lifeline of an AgentRole is split and the thread of interaction defines the reaction to received messages.
• A thread of interaction is shown as a tall thin rectangle whose top is aligned with its initiation time and whose bottom is aligned with its completion time. It is drawn over the lifeline of an AgentRole.
• The following two representations are equivalent.

               

• A message or sending of a communicative act is a communication from one AgentRole to another that conveys information with the expectation that the receiving AgentRole would react according to the semantics of the communicative act. The specification of the protocol says nothing about the implementation of the processing of the communicative act.
• A message sending is shown as a horizontal solid arrow from a thread of interaction of an AgentRole to another thread of interaction of another AgentRole.
• Each arrow is labelled with a message label that has the following syntax:
  predecessor guard-condition sequence-expression communicative-act argument-list
  
  • predecessor This consists of at most one natural number followed by a slash (/) defining the sequencing of a parallel construct or the number of the input and output parameter.
  • guard-conditionThis is a usual UML guard condition, with the semantics, that the message is sent iff the guard is true.
  • sequence-expression This is a constraint, especially with n..m which denotes that the message is sent n up to m times.
  • communicative-act This is either the name, that is, a string representation with an underlined name, of a concrete communicative act instance, the name of a concrete communicative act instance and its associated communicative act, written as name:communicative-act or only the name of the communicative act, for example, inform.
  • argument-listThis is a comma-separated list of arguments enclosed in parentheses.

• A parameterised protocol is the description for an IP with one or more unbound formal parameters. It therefore defines a family of protocols, each protocol specified by binding the parameters to actual values.
• A small dashed rectangle is superimposed on the upper right-hand corner of the rectangle with rounded corners as when defining a nested protocol. The dashed rectangle contains a parameter list of formal parameters for the protocol.
• Communicative act can be marked with an asterisk in the parameter specification, denoting different kinds of messages that can alternatively be sent in this context.

• Real world issues of cancelling actions, asynchrony, abnormal or unexpected IP termination, nested IPs, and the like, are explicitly not addressed here.

After receiving the bids, the Initiator can either (xor):

1. reject-proposal-1
2. accept-proposal
3. First refect-proposal-2, then cfp-2 (and we repeat...)

• Even though the auction will continue for as long as there is at least one bidder, the agents will need to know whether their bid (represented by the propose act) has been accepted. Hence the appearance in the IP of the accept-proposal and reject-proposal acts, despite this being implicit in the English Auction process that is being modelled.
• At the end of the IP, the auctioneer will typically enter a request IP (see [FIPA00026]) with the winning bidder to complete the auction transaction